
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <climits>
#include <cfloat>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>        



using namespace std;

struct Node {
    int key;
    int color;
    Node* left;
    Node* right;
    Node(int k, int c) {
        key = k;
        color = c;
        left = NULL;
        right = NULL;
    }
};

Node* root = NULL;

void insert(int key) {
    Node* newNode = new Node(key, 1);
    if (root == NULL) {
        root = newNode;
        root->color = 0;
        return;
    }
    Node* temp = root;
    Node* parent = NULL;
    while (temp != NULL) {
        parent = temp;
        if (key < temp->key) {
            temp = temp->left;
        }
        else if (key > temp->key) {
            temp = temp->right;
        }
        else {
            return;
        }
    }
    if (key < parent->key) {
        parent->left = newNode;
    }
    else {
        parent->right = newNode;
    }
    newNode->color = 1;
    insertFix(newNode);
}            

void insertFix(Node* node) {
        Node* parent = NULL;
        Node* grandParent = NULL;
        Node* uncle = NULL;
        while (node->color == 1 && node != root) {
            parent = node->parent;
            grandParent = parent->parent;
            if (parent == grandParent->left) { 
                uncle = grandParent->right;
                if (uncle != NULL && uncle->color == 1) {
                    parent->color = 0;
                    uncle->color = 0;
                    grandParent->color = 1;
                    node = grandParent;
                }